package com.datastructure.test.deletethenodeofsearchtree;

public class DeleteTheNodeOfBinarySearchTree {

    public static void main(String[] args) {

    }

    public TreeNode deleteNode (TreeNode root, int key) {
        // write code here
        if (root == null) return root;
        if (root.val == key) {
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            else {
                TreeNode cur = root.right;
                while (cur.left != null) cur = cur.left;
                cur.left = root.left;
                return root.right;
            }
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        }
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }
}

class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
     this.val = val;
   }
 }